package bamboo.util;

class History[A](defaultValue: A, maxSize: Int) {

  private class HistoryEntry(val elem: A, var prev: HistoryEntry, var next: HistoryEntry)

  private var firstEntry = new HistoryEntry(defaultValue, null, null)
  private var lastEntry: HistoryEntry = _
  private var curEntry = firstEntry
  private var isActive = false
  private var size = 0
  
  def add(value: A) {
    if(value == null) return;
    isActive = false
    if(isRepeatedOrDefault(value)) {
      if(!isEmpty && (firstEntry == curEntry))
        curEntry = firstEntry.next
      return
    }
    insertFirst(value)
    checkIncSize
  }
  
  def fwd = step(curEntry.prev)
  def back = step(curEntry.next)
  
  private def step(to: HistoryEntry) = {
    if(isActive && to != null) 
      curEntry = to
    isActive = true
    curEntry.elem
  }

  private def removeOldest {
    lastEntry.prev.next = null
    lastEntry = lastEntry.prev
  }

  private def checkIncSize {
    if(size < maxSize)
      size += 1
    else
      removeOldest
  }
  
  private def insertFirst(value: A) {
    val newEntry = new HistoryEntry(value, firstEntry, firstEntry.next)
    firstEntry.next = newEntry
    if(newEntry.next != null)
      newEntry.next.prev = newEntry
    else
      lastEntry = newEntry
    curEntry = newEntry
  }
  
  private def isRepeatedOrDefault(value: A) = (!isEmpty && value.equals(firstEntry.next.elem)) || value.equals(defaultValue)
  
  private def isEmpty = firstEntry.next == null
}
